home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / depth1.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  1KB  |  68 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_edit.h>
  3.  
  4.  
  5. void compute_depth(graph& G, node_array<int>& depth)
  6. {
  7.   // reverse all edges and compute longest paths in topological order
  8.   // starting in nodes with indegree 0
  9.   // PRECONDITION: G is acyclic
  10.  
  11.   G.rev();  
  12.  
  13.   node_array<int>  degree(G);
  14.   list<node>       zero_deg;
  15.   node v;
  16.   edge e;
  17.   int  count = 0;
  18.  
  19.   forall_nodes(v,G)
  20.   { depth[v] = 0;
  21.     degree[v] = G.indeg(v);
  22.     if (G.indeg(v) == 0) zero_deg.append(v);
  23.    }
  24.  
  25.   while(! zero_deg.empty())
  26.   { count++;
  27.     v = zero_deg.pop();
  28.     forall_adj_edges(e,v)
  29.     { int  d = depth[v];
  30.       node w = G.target(e);
  31.       if (depth[w] < d+1) depth[w] = d+1;
  32.       if (--degree[w] == 0) zero_deg.append(w);
  33.      }
  34.    }
  35.  
  36.   if (count < G.number_of_nodes()) 
  37.   { cerr << "Error: cyclic graph\n";
  38.     exit(1);
  39.    }
  40.  
  41.   G.rev();  // restore original graph
  42. }
  43.  
  44.  
  45. main()
  46. { 
  47.   GRAPH<point,int> G;
  48.   window W;
  49.   node v;
  50.   edge e;
  51.  
  52.   for(;;)
  53.   { G.clear();
  54.     graph_edit(W,G);
  55.     node_array<int> depth(G);
  56.  
  57.     compute_depth(G,depth);
  58.  
  59.     W.clear();
  60.     forall_nodes(v,G) W.draw_text_node(G[v],string("%d",depth[v]));
  61.     forall_edges(e,G) W.draw_edge_arrow(G[source(e)],G[target(e)]);
  62.  
  63.     if (W.read_mouse() == 3) break;
  64.   }
  65.  
  66.  return 0;
  67. }
  68.